{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "<h1> Challenge Solution: Getting started with TensorFlow </h1>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "## Challenge Exercise\n",
    "\n",
    "Use TensorFlow to find the roots of a fourth-degree polynomial using [Halley's Method](https://en.wikipedia.org/wiki/Halley%27s_method).  The five coefficients (i.e. $a_0$ to $a_4$) of \n",
    "<p>\n",
    "$f(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + a_4 x^4$\n",
    "<p>\n",
    "will be fed into the program, as will the initial guess $x_0$. Your program will start from that initial guess and then iterate one step using the formula:\n",
    "<img src=\"https://wikimedia.org/api/rest_v1/media/math/render/svg/142614c0378a1d61cb623c1352bf85b6b7bc4397\" />\n",
    "<p>\n",
    "If you got the above easily, try iterating indefinitely until the change between $x_n$ and $x_{n+1}$ is less than some specified tolerance. Hint: Use [tf.while_loop](https://www.tensorflow.org/api_docs/python/tf/while_loop)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iterate one step\n",
    "\n",
    "Note that we use TensorFlow's built-in automatic differentiation!"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "7.4111586\n"
     ]
    }
   ],
   "source": [
    "import tensorflow as tf\n",
    "import numpy as np\n",
    "\n",
    "class Halley:\n",
    "  def __init__(self, a):\n",
    "    self.f = lambda x: a[0] + a[1] * x + a[2] * tf.pow(x, 2) + a[3] * tf.pow(x, 3) + a[4] * tf.pow(x, 4)\n",
    "    self.df = lambda x: tf.gradients(self.f(x), x)[0]  # TensorFlow does automatic differentiation!\n",
    "    self.ddf = lambda x: tf.gradients(self.df(x), x)[0]\n",
    "\n",
    "  def compute_one_iteration(self, x):\n",
    "    return x - ((2 * self.f(x) * self.df(x)) / (2 * tf.pow(self.df(x), 2) - self.f(x) * self.ddf(x)))\n",
    "\n",
    "\n",
    "# answer is supposed to be 7.411\n",
    "with tf.Session() as sess:\n",
    "  a = [-1.0,1.0,12.0,-4.0,1.0]\n",
    "  x0 = tf.constant(12.0)\n",
    "  halley = Halley(a)\n",
    "  answer = halley.compute_one_iteration(x0)\n",
    "  result = sess.run(answer)\n",
    "  print(result)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iterate 3 times\n",
    "\n",
    "... by writing the compute 3 times"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "[7.4111586, 4.459961, 2.2138097]\n"
     ]
    }
   ],
   "source": [
    "import tensorflow as tf\n",
    "import numpy as np\n",
    "\n",
    "class Halley:\n",
    "  def __init__(self, a):\n",
    "    self.f = lambda x: a[0] + a[1] * x + a[2] * tf.pow(x, 2) + a[3] * tf.pow(x, 3) + a[4] * tf.pow(x, 4)\n",
    "    self.df = lambda x: tf.gradients(self.f(x), x)[0]\n",
    "    self.ddf = lambda x: tf.gradients(self.df(x), x)[0]\n",
    "\n",
    "  def compute_one_iteration(self, x):\n",
    "    return x - ((2 * self.f(x) * self.df(x)) / (2 * tf.pow(self.df(x), 2) - self.f(x) * self.ddf(x)))\n",
    "\n",
    "\n",
    "# answer is supposed to be [7.4111586, 4.459961, 2.2138097]\n",
    "with tf.Session() as sess:\n",
    "  a = [-1.0,1.0,12.0,-4.0,1.0]\n",
    "  x0 = tf.constant(12.0)\n",
    "  halley = Halley(a)\n",
    "  x1 = halley.compute_one_iteration(x0)\n",
    "  x2 = halley.compute_one_iteration(x1)\n",
    "  x3 = halley.compute_one_iteration(x2)\n",
    "  result = sess.run([x1, x2, x3])\n",
    "  print(result)\n",
    "  "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Iterate until condition\n",
    "... using tf.while"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "collapsed": false
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0.25915924\n"
     ]
    }
   ],
   "source": [
    "import tensorflow as tf\n",
    "import numpy as np\n",
    "\n",
    "import tensorflow as tf\n",
    "import numpy as np\n",
    "\n",
    "class Halley:\n",
    "  def __init__(self, a):\n",
    "    self.f = lambda x: a[0] + a[1] * x + a[2] * tf.pow(x, 2) + a[3] * tf.pow(x, 3) + a[4] * tf.pow(x, 4)\n",
    "    self.df = lambda x: tf.gradients(self.f(x), x)[0]\n",
    "    self.ddf = lambda x: tf.gradients(self.df(x), x)[0]\n",
    "\n",
    "  def compute_one_iteration(self, x):\n",
    "    return x - ((2 * self.f(x) * self.df(x)) / (2 * tf.pow(self.df(x), 2) - self.f(x) * self.ddf(x)))\n",
    "\n",
    "  def prev_and_curr(self, iterno, prev, x):\n",
    "    return iterno+1, x, self.compute_one_iteration(x)\n",
    "\n",
    "  def compute(self, x0, maxiter, epsilon):\n",
    "    return tf.while_loop(lambda i, prev, x: tf.logical_and(tf.abs(prev-x) > epsilon, i < maxiter), \n",
    "                         self.prev_and_curr, (0, x0-2*epsilon, x0))\n",
    "  \n",
    "# init parameters\n",
    "# answer is supposed to be -0.31365424 or 0.259158\n",
    "with tf.Session() as sess:\n",
    "  a = [-1.0,1.0,12.0,-4.0,1.0]\n",
    "  x0 = tf.constant(12.0)\n",
    "  halley = Halley(a)\n",
    "  xn = halley.compute(x0, 100, 0.01)\n",
    "  result = sess.run(xn)\n",
    "  print(result[2])"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "deletable": true,
    "editable": true
   },
   "source": [
    "Copyright 2018 Google Inc. Licensed under the Apache License, Version 2.0 (the \"License\"); you may not use this file except in compliance with the License. You may obtain a copy of the License at http://www.apache.org/licenses/LICENSE-2.0 Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.15"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
